package org.zdw.data.structure.sort;

import org.zdw.data.structure.util.ExecutionCounter;

/**
 *
 *冒泡排序说明：
 *    1）一次比较两个元素，如果他们的顺序错误就把他们交换过来。
 *    2）重复地进行直到没有再需要交换，也就是说已经排序完成。
 *    3）越小的元素会经由交换慢慢“浮”到数列的顶端。
 *
 *冒泡排序算法的运作如下:
 *    1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 *    2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 *    3）针对所有的元素重复以上的步骤，除了最后一个。
 *    4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */
public class BubbleSort implements Sort{

    public void sort(int[] array){
        int temp = 0;
        for (int i = array.length - 1; i > 0; --i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (array[j + 1] < array[j])
                {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
                ExecutionCounter.getInstance().increase();
            }
        }
    }

    /**
     * 冒泡排序改进算法 - 只能减少循环次数
     * @param array
     */
    public void improvedSort(int[] array) {
        int temp = 0;
        for (int i = array.length - 1; i > 0; --i)
        {
            boolean flag = true;
            for (int j = 0; j < i; ++j)
            {
                if (array[j + 1] < array[j])
                {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = false;
                }
                ExecutionCounter.getInstance().increase();
            }

            if(flag){
                break;
            }
        }
    }

    public void improvedSort1(int[] array) {
        int temp = 0;
        int lastSwapIndex = 0;
        int tempLastSwapIndex = 0;
        for (int i = array.length - 1; i > 0; --i)
        {
            boolean flag = true;
            if(lastSwapIndex == 0)
                lastSwapIndex = i;
            else
                lastSwapIndex = tempLastSwapIndex;
            for (int j = 0; j < lastSwapIndex; ++j)
            {
                if (array[j + 1] < array[j])
                {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    tempLastSwapIndex = j;
                    flag = false;
                }
                ExecutionCounter.getInstance().increase();
            }

            if(flag){
                break;
            }
        }
    }
}
